package my.jwds.p15;

import java.util.*;

public class ThreeSum {

    public static void main(String[] args) {

        ThreeSum obj = new ThreeSum();
        long start = System.currentTimeMillis();
        System.out.println(obj.threeSum(new int[]{-4,0,1,3,7,9}));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        int prev = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int num1 = nums[i];
            if (num1 == prev) continue;
            prev = num1;

            int num2Prev = Integer.MAX_VALUE;
            int num3Index = nums.length -1;
            for (int j = i+1; j < num3Index; j++) {
                int num2 = nums[j];
                if (num2 == num2Prev)continue;
                num2Prev = num2;


                int sum = -1;
                while(num3Index!=j){
                    int num3 = nums[num3Index--];
                    sum = num1+num2+num3;
                    if (sum <=0)
                        break;
                }
                if (sum < 0){
                    num3Index ++;
                    continue;
                }
                if (sum == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(num1);
                    list.add(num2);
                    list.add(-num1-num2);
                    res.add(list);
                }

            }


        }
        return res;
    }
}